{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Minimum Number of Frogs Croaking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #counting"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #计数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minNumberOfFrogs"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #数青蛙"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>croakOfFrogs</code>，它表示不同青蛙发出的蛙鸣声（字符串 <code>\"croak\"</code> ）的组合。由于同一时间可以有多只青蛙呱呱作响，所以&nbsp;<code>croakOfFrogs</code> 中会混合多个 <code>“croak”</code> <em>。</em></p>\n",
    "\n",
    "<p>请你返回模拟字符串中所有蛙鸣所需不同青蛙的最少数目。</p>\n",
    "\n",
    "<p>要想发出蛙鸣 \"croak\"，青蛙必须 <strong>依序</strong> 输出 <code>‘c’, ’r’, ’o’, ’a’, ’k’</code> 这 5 个字母。如果没有输出全部五个字母，那么它就不会发出声音。如果字符串 <code>croakOfFrogs</code> 不是由若干有效的 \"croak\" 字符混合而成，请返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>croakOfFrogs = \"croakcroak\"\n",
    "<strong>输出：</strong>1 \n",
    "<strong>解释：</strong>一只青蛙 “呱呱” 两次\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>croakOfFrogs = \"crcoakroak\"\n",
    "<strong>输出：</strong>2 \n",
    "<strong>解释：</strong>最少需要两只青蛙，“呱呱” 声用黑体标注\n",
    "第一只青蛙 \"<strong>cr</strong>c<strong>oak</strong>roak\"\n",
    "第二只青蛙 \"cr<strong>c</strong>oak<strong>roak</strong>\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>croakOfFrogs = \"croakcrook\"\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>给出的字符串不是 \"croak<strong>\"</strong> 的有效组合。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= croakOfFrogs.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li>字符串中的字符只有 <code>'c'</code>, <code>'r'</code>, <code>'o'</code>, <code>'a'</code> 或者 <code>'k'</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [minimum-number-of-frogs-croaking](https://leetcode.cn/problems/minimum-number-of-frogs-croaking/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [minimum-number-of-frogs-croaking](https://leetcode.cn/problems/minimum-number-of-frogs-croaking/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"croakcroak\"', '\"crcoakroak\"', '\"croakcrook\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        c = 0\n",
    "        k = 0\n",
    "        r = 0\n",
    "        a = 0\n",
    "        o = 0 #记录相应字符数量\n",
    "        ans = 0\n",
    "        for i in range(0,len(croakOfFrogs)):\n",
    "            if(croakOfFrogs[i]=='c'):\n",
    "                c += 1\n",
    "            elif(croakOfFrogs[i]=='r'):\n",
    "                r += 1\n",
    "            elif(croakOfFrogs[i]=='o'):\n",
    "                o += 1\n",
    "            elif(croakOfFrogs[i]=='a'):\n",
    "                a += 1\n",
    "            elif(croakOfFrogs[i]=='k'):\n",
    "                k += 1\n",
    "            ans = max(c-k,ans)#前面有K结束，是一只青蛙重复叫，没有k结束，新加入青蛙，c-k是精华\n",
    "            if c>=r and r>=o and o>=a and a>=k:#因为是依次叫的，所以一定符合这个规律\n",
    "                continue\n",
    "            else:\n",
    "                return -1\n",
    "        if(c==a and a==o and o==k and r==c):#二次保证没有叫错的\n",
    "            return ans\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        croak_list = list(croakOfFrogs)\n",
    "        croak_num = [0,0,0,0,0]\n",
    "        frog_num = 0\n",
    "        res = 0\n",
    "        for char in croak_list:\n",
    "            if char == \"c\":\n",
    "                croak_num[0] += 1\n",
    "                frog_num  += 1\n",
    "                res = max(frog_num,res)\n",
    "            elif char == \"r\":\n",
    "                if croak_num[0] <=0:\n",
    "                    return -1\n",
    "                else:\n",
    "                    croak_num[1] += 1\n",
    "                    croak_num[0] -= 1\n",
    "            elif char == \"o\":\n",
    "                if croak_num[1] <=0:\n",
    "                    return -1\n",
    "                else:\n",
    "                    croak_num[2] += 1\n",
    "                    croak_num[1] -= 1\n",
    "            elif char == \"a\":\n",
    "                if croak_num[2] <=0:\n",
    "                    return -1\n",
    "                else:\n",
    "                    croak_num[3] += 1\n",
    "                    croak_num[2] -= 1\n",
    "            else:\n",
    "                if croak_num[3] <=0:\n",
    "                    return -1\n",
    "                else:\n",
    "                    croak_num[3] -= 1\n",
    "                    frog_num -= 1\n",
    "            \n",
    "        for temp in croak_num:\n",
    "            if temp!=0:\n",
    "                return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\r\n",
    "\r\n",
    "        croak_list = list(croakOfFrogs)\r\n",
    "        # croak_num用来记录c,r,o,a,k每个字母当前出现的次数\r\n",
    "        croak_num = [0,0,0,0,0] \r\n",
    "        # 记录当前青蛙的个数，当遇到c时，当前青蛙数加1，当遇到k时，当前青蛙数减1 \r\n",
    "        frog_num = 0\r\n",
    "        # 记录最后返回的结果，因为frog_num是会随时间变化的，所以我们要记录下frog_num的最大值，作为最后的返回结果\r\n",
    "        res = 0\r\n",
    "        # 字符按照c=>r=>o=>a=>k的顺序出现，则依次对当前位的数字次数加1，并对当前字母的前一个字母出现次数减1\r\n",
    "        # 如果不是按照上述顺序出现，比如r出现了，但是前面没有c，则直接返回-1\r\n",
    "        # 最后所有字符的次数都应该为0\r\n",
    "        for char in croak_list:\r\n",
    "            if char == \"c\":\r\n",
    "                croak_num[0] += 1\r\n",
    "                frog_num  += 1\r\n",
    "                res = max(frog_num,res)\r\n",
    "            elif char == \"r\":\r\n",
    "                if croak_num[0] <=0:\r\n",
    "                    return -1\r\n",
    "                else:\r\n",
    "                    croak_num[1] += 1\r\n",
    "                    croak_num[0] -= 1\r\n",
    "            elif char == \"o\":\r\n",
    "                if croak_num[1] <=0:\r\n",
    "                    return -1\r\n",
    "                else:\r\n",
    "                    croak_num[2] += 1\r\n",
    "                    croak_num[1] -= 1\r\n",
    "            elif char == \"a\":\r\n",
    "                if croak_num[2] <=0:\r\n",
    "                    return -1\r\n",
    "                else:\r\n",
    "                    croak_num[3] += 1\r\n",
    "                    croak_num[2] -= 1\r\n",
    "            else:\r\n",
    "                if croak_num[3] <=0:\r\n",
    "                    return -1\r\n",
    "                else:\r\n",
    "                    croak_num[3] -= 1\r\n",
    "                    frog_num -= 1\r\n",
    "                    \r\n",
    "        #  最后检查一遍所有字符的出现次数是不是都归0了，以此判断字符串是不是croak的若干组合 \r\n",
    "        for temp in croak_num:\r\n",
    "            if temp!=0:\r\n",
    "                return -1\r\n",
    "        return res\r\n",
    "\r\n",
    "\r\n",
    "            \r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5:\n",
    "            return -1\n",
    "        res, frog_num = 0, 0\n",
    "        cnt = [0] * 4\n",
    "        mp = {'c':0, 'r':1, 'o':2, 'a':3, 'k':4}\n",
    "        for c in croakOfFrogs:\n",
    "            t = mp[c]\n",
    "            if t == 0:\n",
    "                cnt[t] += 1\n",
    "                frog_num += 1\n",
    "                if frog_num > res:\n",
    "                    res = frog_num\n",
    "            else:\n",
    "                if cnt[t - 1] == 0:\n",
    "                    return -1\n",
    "                cnt[t - 1] -= 1\n",
    "                if t == 4:\n",
    "                    frog_num -= 1\n",
    "                else:\n",
    "                    cnt[t] += 1\n",
    "        if frog_num > 0:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5:\n",
    "            return -1\n",
    "\n",
    "        voice = {'c': 0, 'r': 1, 'o': 2, 'a': 3, 'k': 4}\n",
    "        # 首先假设有五个坑，放叫声在第x状态的青蛙数量,无需存储第五个状态，所以*4\n",
    "        frogs = [0] * 4\n",
    "        res = 0\n",
    "        curr = 0  # 当前青蛙数量\n",
    "        for w in croakOfFrogs:\n",
    "            x = voice[w]  # 叫声状态\n",
    "           \n",
    "            if x == 0:  # 如果是第一声a,就加一只青蛙,更新一次res\n",
    "                frogs[0] += 1\n",
    "                curr += 1\n",
    "                res = max(curr, res)\n",
    "            else:\n",
    "                if frogs[x - 1] == 0:  # 不是第一声的情况下，则需要判断，是否和前面的接的上\n",
    "                    return -1\n",
    "\n",
    "                frogs[x - 1] -= 1  # 给前一声的青蛙数量-1\n",
    "                if x == 4:  # 如果是最后一声k，青蛙数量-1\n",
    "                    curr -= 1\n",
    "                else:  # 否则给当前这一声数量+1\n",
    "                    frogs[x] += 1\n",
    "     \n",
    "        return res if curr == 0 else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        mp = defaultdict()\n",
    "        for idx, ch in enumerate(\"croak\"):\n",
    "            mp[ch] = idx\n",
    "        cnt = [0] * 4\n",
    "        ret = 0\n",
    "        frogs = 0\n",
    "\n",
    "        for ch in croakOfFrogs:\n",
    "            idx = mp[ch]\n",
    "\n",
    "            if idx == 0:\n",
    "                frogs += 1\n",
    "\n",
    "                if frogs > ret:\n",
    "                    ret = frogs\n",
    "                cnt[idx] += 1\n",
    "            else:\n",
    "                if cnt[idx - 1] <= 0:\n",
    "                    return -1\n",
    "                cnt[idx-1] -= 1\n",
    "\n",
    "                if idx == 4:\n",
    "                    frogs -= 1\n",
    "                else:\n",
    "                    cnt[idx] += 1\n",
    "        return ret if frogs <= 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        croak_index = {e: i for i, e in enumerate(\"croak\")}\n",
    "        data = defaultdict(int)\n",
    "        data[-1] = float(\"inf\")\n",
    "        n = len(croakOfFrogs)\n",
    "        diff = [0] * n\n",
    "        count = 0\n",
    "        rs = 0\n",
    "        for i, c in enumerate(croakOfFrogs):\n",
    "            if data[croak_index[c]] < data[croak_index[c] - 1]:  # 只记录符合顺序的croak\n",
    "                data[croak_index[c]] += 1\n",
    "                if c == \"c\":\n",
    "                    diff[i] += 1\n",
    "                elif c == \"k\":\n",
    "                    diff[i] -= 1\n",
    "                count += diff[i]\n",
    "                rs = max(rs, count)\n",
    "        return rs if data[croak_index[\"k\"]] * 5 == n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        n=len(croakOfFrogs)\n",
    "        ck=[0]*5\n",
    "        res=0\n",
    "        for x in croakOfFrogs:\n",
    "            if x==\"c\":\n",
    "                ck[0]+=1\n",
    "                res=max(res,ck[0])\n",
    "            elif x==\"r\":\n",
    "                ck[1]+=1\n",
    "                for i in range(1):\n",
    "                    if ck[i]<ck[1]:\n",
    "                        return -1\n",
    "            \n",
    "            elif x==\"o\":\n",
    "                ck[2]+=1\n",
    "                for i in range(2):\n",
    "                    if ck[i]<ck[2]:\n",
    "                        return -1\n",
    "\n",
    "            elif x==\"a\":\n",
    "                ck[3]+=1\n",
    "                for i in range(3):\n",
    "                    if ck[i]<ck[3]:\n",
    "                        return -1\n",
    "            else:\n",
    "                ck[4]+=1\n",
    "                for i in range(4):\n",
    "                    if ck[i]<ck[4]:\n",
    "                        return -1\n",
    "                for i in range(5):\n",
    "                    ck[i]-=ck[4]\n",
    "\n",
    "        if sum(ck)==0:\n",
    "            return res\n",
    "        return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5:\n",
    "            return -1\n",
    "        c,r,o,a,k=0,0,0,0,0\n",
    "        res=0\n",
    "        for ch in croakOfFrogs:\n",
    "            if ch=='c':\n",
    "                if k>0:\n",
    "                    k-=1\n",
    "                c+=1\n",
    "            elif ch=='r':\n",
    "                r+=1\n",
    "                c-=1\n",
    "                if c<0:\n",
    "                    return -1\n",
    "            elif ch=='o':\n",
    "                r-=1\n",
    "                o+=1\n",
    "                if r<0:\n",
    "                    return -1\n",
    "            elif ch=='a':\n",
    "                o-=1\n",
    "                a+=1\n",
    "                if o<0:\n",
    "                    return -1\n",
    "            else:\n",
    "                a-=1\n",
    "                k+=1\n",
    "                if a<0:\n",
    "                    return -1\n",
    "        return -1 if c or r or o or a else k\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        lst = [0] * 5\n",
    "        for ch in croakOfFrogs:\n",
    "            if ch == 'c':\n",
    "                if lst[4]:\n",
    "                    lst[4] -= 1\n",
    "                lst[0] += 1\n",
    "            elif ch == 'r':\n",
    "                if lst[0]:\n",
    "                    lst[0] -= 1\n",
    "                    lst[1] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            elif ch == 'o':\n",
    "                if lst[1]:\n",
    "                    lst[1] -= 1\n",
    "                    lst[2] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            elif ch == 'a':\n",
    "                if lst[2]:\n",
    "                    lst[2] -= 1\n",
    "                    lst[3] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            elif ch == 'k':\n",
    "                if lst[3]:\n",
    "                    lst[3] -= 1 \n",
    "                    lst[4] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "        return -1 if any(lst[:4]) else lst[4]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5 > 0:\n",
    "            return -1\n",
    "        cnt = [0] * 5\n",
    "        croak = ['c', 'r', 'o', 'a', 'k']\n",
    "        res = 0\n",
    "        frog_num = 0\n",
    "        for croakOfFrog in croakOfFrogs:\n",
    "            i = croak.index(croakOfFrog)\n",
    "            if i == 0:\n",
    "                frog_num += 1\n",
    "                cnt[i] += 1\n",
    "                if res < frog_num:\n",
    "                    res = frog_num\n",
    "            else:\n",
    "                if cnt[i-1] == 0:\n",
    "                    return -1\n",
    "                cnt[i-1] -= 1\n",
    "                if i == 4:\n",
    "                    frog_num -= 1\n",
    "                else:\n",
    "                    cnt[i] += 1\n",
    "        if frog_num != 0:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5:\n",
    "            return -1\n",
    "        res, frog_num = 0, 0\n",
    "        cnt = [0] * 4\n",
    "        mp = {'c':0, 'r':1, 'o':2, 'a':3, 'k':4}\n",
    "        for c in croakOfFrogs:\n",
    "            t = mp[c]\n",
    "            if t == 0:\n",
    "                cnt[t] += 1\n",
    "                frog_num += 1\n",
    "                if frog_num > res:\n",
    "                    res = frog_num\n",
    "            else:\n",
    "                if cnt[t - 1] == 0:\n",
    "                    return -1\n",
    "                cnt[t - 1] -= 1\n",
    "                if t == 4:\n",
    "                    frog_num -= 1\n",
    "                else:\n",
    "                    cnt[t] += 1\n",
    "        if frog_num > 0:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "PREVIOUS = dict(pairwise(\"croakc\"[::-1]))\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        cnt = Counter()\n",
    "        for ch in croakOfFrogs:\n",
    "            pre = PREVIOUS[ch]  # pre 为 ch 在 \"croak\" 中的上一个字母\n",
    "            if cnt[pre]:  # 如果有青蛙发出了 pre 的声音\n",
    "                cnt[pre] -= 1  # 复用一只\n",
    "            elif ch != 'c':  # 否则青蛙必须从 'c' 开始蛙鸣\n",
    "                return -1  # 不符合要求\n",
    "            cnt[ch] += 1  # 发出了 ch 的声音\n",
    "        if any(cnt[ch] for ch in \"croa\"):\n",
    "            return -1  # 有发出其它声音的青蛙，不符合要求\n",
    "        return cnt['k']  # 最后青蛙们都发出了 'k' 的声音"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        c = r = o = a = k = 0\n",
    "        ans = 0\n",
    "        for i in range(0, len(croakOfFrogs)):\n",
    "            if croakOfFrogs[i] == 'c':\n",
    "                c += 1\n",
    "            elif croakOfFrogs[i] == 'r':\n",
    "                r += 1\n",
    "            elif croakOfFrogs[i] == 'o':\n",
    "                o += 1\n",
    "            elif croakOfFrogs[i] == 'a':\n",
    "                a += 1\n",
    "            elif croakOfFrogs[i] == 'k':\n",
    "                o -= 1\n",
    "                r -= 1\n",
    "                c -= 1\n",
    "                a -= 1\n",
    "            ans = max(c, ans)\n",
    "            if c<a or r<o or o<a or c<r:\n",
    "                return -1\n",
    "        if c == r == o == a == 0:\n",
    "            return ans\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        c = r = o = a = 0\n",
    "        ans = 0\n",
    "        for i in range(0, len(croakOfFrogs)):\n",
    "            if croakOfFrogs[i] == 'c':\n",
    "                c += 1\n",
    "            elif croakOfFrogs[i] == 'r':\n",
    "                r += 1\n",
    "            elif croakOfFrogs[i] == 'o':\n",
    "                o += 1\n",
    "            elif croakOfFrogs[i] == 'a':\n",
    "                a += 1\n",
    "            else:\n",
    "                c -= 1\n",
    "                r -= 1\n",
    "                o -= 1\n",
    "                a -= 1\n",
    "            ans = max(c, ans)\n",
    "            if r<o or o<a or c<r:\n",
    "                return -1\n",
    "        if c ==  a == 0:\n",
    "            return ans\n",
    "        else:\n",
    "            return -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5: return -1\n",
    "\n",
    "        res, frog_num = 0, 0\n",
    "        cnt = [0] * 4\n",
    "        mp = {'c': 0, 'r': 1, 'o': 2, 'a':3, 'k':4}\n",
    "        for c in croakOfFrogs:\n",
    "            index = mp[c]\n",
    "            if index == 0:\n",
    "                cnt[index] += 1\n",
    "                frog_num += 1\n",
    "                res = max(res, frog_num)\n",
    "            else:\n",
    "                if cnt[index - 1] == 0: return -1\n",
    "                cnt[index - 1] -= 1\n",
    "                if index == 4: frog_num -= 1\n",
    "                else: cnt[index] += 1\n",
    "        if frog_num > 0: return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理每个字母在 \"croak\" 中的上一个字母\n",
    "# PREVIOUS = dict(pairwise(\"croakc\"[::-1]))\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        # pre = dict(pairwise(\"croakc\"[::-1]))\n",
    "        pre = dict(zip(\"roakc\", \"croak\"))\n",
    "        d = collections.defaultdict(int)\n",
    "        for ch in croakOfFrogs:\n",
    "            p = pre[ch]\n",
    "            if d[p]:\n",
    "                d[p] -= 1\n",
    "            elif ch != \"c\":\n",
    "                return -1\n",
    "            d[ch] += 1\n",
    "        if any(d[ch] for ch in \"croa\"):\n",
    "            return -1\n",
    "        return d[\"k\"]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        cnt={\"c\":0,\"r\":0,\"o\":0,\"a\":0,\"k\":0}\n",
    "        pre={\"r\":\"c\",\"o\":\"r\",\"a\":\"o\",\"k\":\"a\"}\n",
    "        ans=0\n",
    "        for ch in croakOfFrogs:\n",
    "            cnt[ch]+=1\n",
    "            if ch==\"c\":\n",
    "                ans=max(ans,cnt[\"c\"]-cnt[\"k\"])\n",
    "            elif cnt[ch]>cnt[pre[ch]]:\n",
    "                return -1\n",
    "        return ans  if cnt[\"c\"]==cnt[\"k\"] else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        s = {'c':0, 'r':1, 'o':2, 'a':3, 'k':4}\n",
    "        cnt = [0] * 5\n",
    "        num, ans = 0, 0\n",
    "        for ch in croakOfFrogs:\n",
    "            cnt[s[ch]] += 1\n",
    "            if ch == 'c':\n",
    "                num += 1   # 发声的青蛙数目+1\n",
    "                ans = max(ans, num)\n",
    "            elif cnt[s[ch]] > cnt[s[ch] - 1]:\n",
    "                return -1\n",
    "            if ch == 'k':\n",
    "                num -= 1   # 发声的青蛙数目-1\n",
    "        return -1 if num else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5 != 0:\n",
    "            return -1\n",
    "\n",
    "        croak = ['c', 'r', 'o', 'a', 'k']\n",
    "        state = {}\n",
    "        curr, ans = 0, 0\n",
    "\n",
    "        for c in croakOfFrogs:\n",
    "            if c == croak[0]:\n",
    "                state[croak[1]] = state.get(croak[1], 0) + 1\n",
    "                curr += 1\n",
    "                ans = max(ans, curr)\n",
    "            \n",
    "            else:\n",
    "                count = state.get(c, 0)\n",
    "                if count > 0:\n",
    "                    state[c] = count - 1\n",
    "                    for i in range(5): \n",
    "                        if croak[i] == c:\n",
    "                            pos = i\n",
    "                    \n",
    "                    if pos == 4:\n",
    "                        curr -= 1\n",
    "                    else:\n",
    "                        state[croak[pos + 1]] = state.get(croak[pos + 1], 0) + 1\n",
    "                else:\n",
    "                    return -1\n",
    "        \n",
    "        return ans if curr == 0 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        cnt = {\"c\":0, \"r\":0, \"o\":0, \"a\":0, \"k\":0}\n",
    "        d = {\"r\":\"c\", \"o\":\"r\", \"a\":\"o\", \"k\":\"a\"}\n",
    "        ans = 0\n",
    "        for ch in croakOfFrogs:\n",
    "            cnt[ch] += 1\n",
    "            if ch != \"c\" and cnt[ch] > cnt[d[ch]]:\n",
    "                return -1\n",
    "            ans = max(ans, cnt[\"c\"] - cnt[\"k\"])\n",
    "        return ans if len(set(cnt.values())) == 1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        '''\n",
    "        \"crcoakroackroak\" -> 2, 第一只叫 -> 第二只叫 -> 第一只叫\n",
    "        '''\n",
    "        rst = float('-inf')\n",
    "        frog_num = 0\n",
    "        cnt = [0] * 4\n",
    "        mapping = {i:j for i, j in zip('croak', list(range(5)))}\n",
    "\n",
    "        for c in croakOfFrogs:\n",
    "            idx = mapping[c]\n",
    "            if idx == 0:\n",
    "                frog_num += 1\n",
    "                cnt[idx] += 1\n",
    "                rst = max(rst, frog_num)\n",
    "            else:\n",
    "                if cnt[idx - 1] == 0:\n",
    "                    return -1\n",
    "\n",
    "                if idx == 4:\n",
    "                    frog_num -= 1\n",
    "                else:\n",
    "                    cnt[idx] += 1\n",
    "\n",
    "                cnt[idx - 1] -= 1\n",
    "\n",
    "        if frog_num != 0:\n",
    "            return -1\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        mp={'c':0,'r':1,'o':2,'a':3,'k':4}\n",
    "        dic={k: 0 for k in range(5)}\n",
    "        for c in croakOfFrogs:\n",
    "            if c=='c':\n",
    "                if dic[4]>0:\n",
    "                    dic[4]-=1\n",
    "                dic[0]+=1\n",
    "            else:\n",
    "                if dic[mp[c]-1]>0:\n",
    "                    dic[mp[c]-1]-=1\n",
    "                else:\n",
    "                    return -1\n",
    "                dic[mp[c]]+=1\n",
    "        print(dic)\n",
    "        for i in range(4):\n",
    "            if dic[i]:\n",
    "                return -1\n",
    "        return dic[4]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5 != 0:\n",
    "            return -1\n",
    "        cnt = [0] * 5\n",
    "        mp = {'c': 0, 'r': 1, 'o': 2, 'a': 3, 'k': 4}\n",
    "        current = 0\n",
    "        res = 0\n",
    "        for alpha in croakOfFrogs:\n",
    "            index = mp[alpha]\n",
    "            if index == 0:\n",
    "                cnt[index] += 1\n",
    "                current += 1\n",
    "            else:\n",
    "                if cnt[index - 1] > 0:\n",
    "                    cnt[index] += 1\n",
    "                    cnt[index - 1] -= 1\n",
    "                    if index == 4:\n",
    "                        res = max(res, current)\n",
    "                        current -= 1\n",
    "                else:\n",
    "                    return -1\n",
    "        if cnt[0] == 0 and cnt[1] == 0 and cnt[2] == 0 and cnt[3] == 0:\n",
    "            return res\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        c = r = o = a = k = 0\n",
    "        ans = 0\n",
    "\n",
    "        for char in croakOfFrogs:\n",
    "            if char == 'c':\n",
    "                c += 1\n",
    "            elif char == 'r':\n",
    "                r += 1\n",
    "            elif char == 'o':\n",
    "                o += 1\n",
    "            elif char == 'a':\n",
    "                a += 1\n",
    "            elif char == 'k':\n",
    "                k += 1\n",
    "            else:\n",
    "                return -1\n",
    "            if not(c >= r and r >= o and o >= a and a >= k):\n",
    "                return -1\n",
    "            ans = max(ans, c - k)\n",
    "        return ans if c == r == o == a == k else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5:\n",
    "            return -1\n",
    "        res,frog_num = 0,0 # 记录所有青蛙个数以及当前正在叫的青蛙个数\n",
    "        cnt = [0]*4  # 当前发出 c r o a 的青蛙数量\n",
    "        maps = {\"c\":0,\"r\":1,\"o\":2,\"a\":3,\"k\":4}\n",
    "        for i in croakOfFrogs:\n",
    "            idx = maps[i]\n",
    "            if idx == 0:\n",
    "                # 发出c和当前叫的青蛙数量都加一: 这种说明下一个发出r的青蛙数量也增加一\n",
    "                cnt[idx] += 1 \n",
    "                frog_num += 1\n",
    "                res = max(res,frog_num)\n",
    "            else:\n",
    "                # 当前如果为r,说明发出叫声c的青蛙数量-1,跳转到发出r的青蛙数量加一\n",
    "                # 但如果没有发出叫声c的青蛙,直接return -1 \n",
    "                if cnt[idx-1] == 0: return -1\n",
    "                cnt[idx-1] -= 1\n",
    "                if idx == 4:\n",
    "                    frog_num -= 1\n",
    "                else:\n",
    "                    cnt[idx] += 1\n",
    "\n",
    "        if frog_num > 0:\n",
    "            # 字符遍历结束但当前仍有在叫的青蛙\n",
    "            return -1\n",
    "        else:\n",
    "            return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        cnt = {\"c\":0, \"r\":0, \"o\":0, \"a\":0, \"k\":0}\n",
    "        d = {\"r\":\"c\", \"o\":\"r\", \"a\":\"o\", \"k\":\"a\"}\n",
    "        ans = 0\n",
    "        for ch in croakOfFrogs:\n",
    "            cnt[ch] += 1\n",
    "            if ch != \"c\" and cnt[ch] > cnt[d[ch]]:\n",
    "                return -1\n",
    "            ans = max(ans, cnt[\"c\"] - cnt[\"k\"])\n",
    "        return ans if len(set(cnt.values())) == 1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs)%5 !=0 : return -1\n",
    "        ans = 0\n",
    "        count_list = {\"c\":0,\"r\":0,\"o\":0,\"a\":0,\"k\":0}\n",
    "        \n",
    "        for i in croakOfFrogs:\n",
    "            if i not in count_list:\n",
    "                return -1\n",
    "            else:\n",
    "                count_list[i] += 1\n",
    "\n",
    "            if not(count_list[\"c\"]>=count_list[\"r\"] and count_list[\"r\"]>=count_list[\"o\"] and count_list[\"o\"]>=count_list[\"a\"] and count_list[\"a\"]>=count_list[\"k\"]):\n",
    "                return -1\n",
    "            # 自己做错了,本来以为这个思路行不通,但这里应该减去count[\"k\"]而不是\"r\",改了之后就正确了\n",
    "            # ans = max(ans,count_list[\"c\"]-count_list[\"r\"])\n",
    "            ans = max(ans,count_list[\"c\"]-count_list[\"k\"])\n",
    "        \n",
    "        if count_list[\"c\"]==count_list[\"r\"]==count_list[\"o\"]==count_list[\"a\"]==count_list[\"k\"]:\n",
    "            # 必须保证完整的蛙鸣\n",
    "            return ans\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5:\n",
    "            return -1\n",
    "        res, frog_num = 0, 0\n",
    "        cnt = [0] * 4\n",
    "        mp = {'c':0, 'r':1, 'o':2, 'a':3, 'k':4}\n",
    "        for c in croakOfFrogs:\n",
    "            t = mp[c]\n",
    "            if t == 0:\n",
    "                cnt[t] += 1\n",
    "                frog_num += 1\n",
    "                if frog_num > res:\n",
    "                    res = frog_num\n",
    "            else:\n",
    "                if cnt[t - 1] == 0:\n",
    "                    return -1\n",
    "                cnt[t - 1] -= 1\n",
    "                if t == 4:\n",
    "                    frog_num -= 1\n",
    "                else:\n",
    "                    cnt[t] += 1\n",
    "        if frog_num > 0:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "\n",
    "        # croakOfFrogs*=20000\n",
    "\n",
    "        before_frogs = [0,0,0,0,0]\n",
    "        croak_index = {\"c\":0, \"r\":1, \"o\":2,\"a\":3, \"k\":4}\n",
    "\n",
    "        frog_number = 0\n",
    "        left_frog_number = 0\n",
    "        for cur_croak in croakOfFrogs:\n",
    "            if cur_croak == \"c\":\n",
    "                before_frogs[0] += 1\n",
    "                if not left_frog_number:\n",
    "                    frog_number += 1\n",
    "                else:\n",
    "                    left_frog_number -= 1\n",
    "            else:\n",
    "                cur_index = croak_index.get(cur_croak)\n",
    "                if  cur_index is None:\n",
    "                    return -1\n",
    "                if before_frogs[cur_index-1]==0:\n",
    "                    return -1\n",
    "                before_frogs[cur_index-1] -= 1\n",
    "                before_frogs[cur_index] += 1\n",
    "                if cur_croak == \"k\":\n",
    "                    left_frog_number += 1\n",
    "        \n",
    "        if (before_frogs[0]==0) and (before_frogs[1]==0) and (before_frogs[2]==0) and (before_frogs[3]==0):\n",
    "            return frog_number\n",
    "        return -1\n",
    "                \n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        count = collections.Counter()\n",
    "        ans = 0\n",
    "        s = 'kaorc'\n",
    "        for c in croakOfFrogs:\n",
    "            count[c] += 1\n",
    "            for k in range(4):\n",
    "                if count[s[k]] > count[s[k+1]]:\n",
    "                    return -1\n",
    "            ans = max(ans, max(count.values()))\n",
    "            if len(count) == 5:\n",
    "                minv = min(count.values())\n",
    "                delet = []\n",
    "                for key in count.keys():\n",
    "                    count[key] -= minv\n",
    "                    if count[key] == 0:\n",
    "                        delet.append(key)\n",
    "                for key in delet:\n",
    "                    count.pop(key)\n",
    "            \n",
    "        return ans if sum(count.values()) == 0 else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "TABLE = {'c':0, 'r':1, 'o':2, 'a':3, 'k':4}\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        l = [0] * 5\n",
    "        ans = 0\n",
    "        for c in croakOfFrogs:\n",
    "            i = TABLE[c]\n",
    "            l[i] += 1\n",
    "            if l[i-1]:\n",
    "                l[i-1] -= 1\n",
    "            elif i:\n",
    "                return -1\n",
    "        \n",
    "        return -1 if any(l[:-1]) else l[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        n = len(croakOfFrogs)\n",
    "        p = {}\n",
    "        croak = {'o' :'r', 'a':'o', 'r':'c', 'k':'a'}\n",
    "        for n in range(n):\n",
    "            c = croakOfFrogs[n]\n",
    "            \n",
    "            if c == 'c':\n",
    "                if p.get('k', 0) != 0:\n",
    "                    tmp = p.get('k', 0)\n",
    "                    p['k'] = tmp - 1 \n",
    "                tmp = p.get(c, 0)\n",
    "                p[c] = tmp + 1\n",
    "            else:\n",
    "                if c not in \"croak\":\n",
    "                    return -1\n",
    "                before = croak.get(c)\n",
    "                tmp = p.get(before, 0)\n",
    "                if tmp == 0:\n",
    "                    return -1\n",
    "                p[before] = tmp - 1\n",
    "                tmp = p.get(c, 0)\n",
    "                p[c] = tmp + 1\n",
    "            count = p.get('c', 0) + p.get('r', 0) + p.get('0', 0) +p.get('a', 0)\n",
    "        return p['k'] if p['k'] and count == 0 else -1\n",
    "\n",
    "\n",
    "                    \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        s = {'c':0, 'r':1, 'o':2, 'a':3, 'k':4}\n",
    "        cnt = [0] * 5\n",
    "        num, ans = 0, 0\n",
    "        for ch in croakOfFrogs:\n",
    "            cnt[s[ch]] += 1\n",
    "            if ch == 'c':\n",
    "                num += 1   # 发声的青蛙数目+1\n",
    "                ans = max(ans, num)\n",
    "            elif cnt[s[ch]] > cnt[s[ch] - 1]:\n",
    "                return -1\n",
    "            if ch == 'k':\n",
    "                num -= 1   # 发声的青蛙数目-1\n",
    "        return -1 if num else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "TABLE = {'c':0, 'r':1, 'o':2, 'a':3, 'k':4}\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        l = [0] * 5\n",
    "        for c in croakOfFrogs:\n",
    "            i = TABLE[c]\n",
    "            if l[i - 1]:\n",
    "                l[i - 1] -= 1\n",
    "            elif i:\n",
    "                return -1\n",
    "            l[i] += 1\n",
    "        \n",
    "        return -1 if any(l[:-1]) else l[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        '''\n",
    "        \"crcoakroackroak\" -> 2, 第一只叫 -> 第二只叫 -> 第一只叫\n",
    "        '''\n",
    "\n",
    "        frog_num = 0\n",
    "        cnt = [0] * 4\n",
    "        mapping = {i:j for i,j in zip('croak', list(range(5)))}\n",
    "        rst = float('-inf')\n",
    "\n",
    "        for c in croakOfFrogs:\n",
    "            idx = mapping[c]\n",
    "            if idx == 0:\n",
    "                frog_num += 1\n",
    "                cnt[idx] += 1\n",
    "                rst = max(rst, frog_num)\n",
    "            else:\n",
    "                if cnt[idx - 1] == 0:\n",
    "                    return -1\n",
    "                cnt[idx - 1] -= 1\n",
    "                \n",
    "                if idx == 4:\n",
    "                    frog_num -= 1\n",
    "                else:\n",
    "                    cnt[idx] += 1\n",
    "\n",
    "        if frog_num == 0:\n",
    "            return rst\n",
    "        return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5:\n",
    "            return -1\n",
    "        res, frog_num = 0, 0\n",
    "        cnt = [0] * 4\n",
    "        mp = {'c':0, 'r':1, 'o':2, 'a':3, 'k':4}\n",
    "        for c in croakOfFrogs:\n",
    "            t = mp[c]\n",
    "            if t == 0:\n",
    "                cnt[t] += 1\n",
    "                frog_num += 1\n",
    "                if frog_num > res:\n",
    "                    res = frog_num\n",
    "            else:\n",
    "                if cnt[t - 1] == 0:\n",
    "                    return -1\n",
    "                cnt[t - 1] -= 1\n",
    "                if t == 4:\n",
    "                    frog_num -= 1\n",
    "                else:\n",
    "                    cnt[t] += 1\n",
    "        if frog_num > 0:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    PREVIOUS = dict(pairwise(\"croakc\"[::-1]))\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        n = len(croakOfFrogs)\n",
    "        c, r, o, a, k = 0, 0, 0, 0, 0\n",
    "        ans = 0\n",
    "        for car in croakOfFrogs:\n",
    "            if car == 'c':\n",
    "                c += 1\n",
    "            elif car =='r':\n",
    "                r += 1\n",
    "            elif car =='o':\n",
    "                o += 1\n",
    "            elif car =='a':\n",
    "                a += 1\n",
    "            elif car == 'k':\n",
    "                k += 1\n",
    "            else:\n",
    "                return -1\n",
    "            if not((c>=r) and (r >= o) and (o >= a) and (a >= k)):\n",
    "                return -1\n",
    "            ans = max(ans, c- k)\n",
    "        if (c == r ) and (r == o) and (o == a) and (a == k):\n",
    "            return ans\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理每个字母在 \"croak\" 中的上一个字母\n",
    "PREVIOUS = dict(pairwise(\"croakc\"[::-1]))\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        cnt = Counter()\n",
    "        if len(croakOfFrogs)% 5 != 0:\n",
    "            return -1\n",
    "        for ch in croakOfFrogs:\n",
    "            pre = PREVIOUS[ch]  # pre 为 ch 在 \"croak\" 中的上一个字母\n",
    "            if cnt[pre]:  # 如果有青蛙发出了 pre 的声音\n",
    "                cnt[pre] -= 1  # 复用一只\n",
    "            elif ch != 'c':  # 否则青蛙必须从 'c' 开始蛙鸣\n",
    "                return -1  # 不符合要求\n",
    "            cnt[ch] += 1  # 发出了 ch 的声音\n",
    "        if any(cnt[ch] for ch in \"croa\"):\n",
    "            return -1  # 有发出其它声音的青蛙，不符合要求\n",
    "        return cnt['k']  # 最后青蛙们都发出了 'k' 的声音"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        h = {'c': 0, 'r': 0, 'o': 0, 'a': 0, 'k': 0}\n",
    "\n",
    "        def serach(h):\n",
    "            max_value = -1\n",
    "            min_value = 1000000\n",
    "            for key in h:\n",
    "                if h[key] > max_value:\n",
    "                    max_value = h[key]\n",
    "                if h[key] < min_value:\n",
    "                    min_value = h[key]\n",
    "            return min_value, max_value\n",
    "\n",
    "        ans = 0\n",
    "        for c in croakOfFrogs:\n",
    "            h[c] += 1\n",
    "            for index, key in enumerate(h):\n",
    "                if index == 0:\n",
    "                    tag = h[key]\n",
    "                    continue\n",
    "                if tag < h[key]:\n",
    "                    return -1\n",
    "                tag = h[key]\n",
    "                \n",
    "            \n",
    "            min_value, max_value = serach(h)\n",
    "            ans = max(max_value - min_value, ans)\n",
    "        if max_value == min_value:\n",
    "            return ans\n",
    "        return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        lst = [0] * 5\n",
    "        for ch in croakOfFrogs:\n",
    "            if ch == 'c':\n",
    "                if lst[4]:\n",
    "                    lst[4] -= 1\n",
    "                lst[0] += 1\n",
    "            elif ch == 'r':\n",
    "                if lst[0]:\n",
    "                    lst[0] -= 1\n",
    "                    lst[1] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            elif ch == 'o':\n",
    "                if lst[1]:\n",
    "                    lst[1] -= 1\n",
    "                    lst[2] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            elif ch == 'a':\n",
    "                if lst[2]:\n",
    "                    lst[2] -= 1\n",
    "                    lst[3] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            elif ch == 'k':\n",
    "                if lst[3]:\n",
    "                    lst[3] -= 1\n",
    "                    lst[4] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "        return -1 if any(lst[:4]) else lst[4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5:\n",
    "            return -1\n",
    "        state = [0,0,0,0,0]\n",
    "        for i in croakOfFrogs:\n",
    "            if i == 'c':\n",
    "                if state[4] > 0:\n",
    "                    state[4] -= 1\n",
    "                state[0] += 1\n",
    "            if i == 'r':\n",
    "                if state[0] == 0:\n",
    "                    return -1\n",
    "                state[0] -= 1\n",
    "                state[1] += 1\n",
    "            if i == 'o':\n",
    "                if state[1] == 0:\n",
    "                    return -1\n",
    "                state[1] -= 1\n",
    "                state[2] += 1\n",
    "            if i == 'a':\n",
    "                if state[2] == 0:\n",
    "                    return -1\n",
    "                state[2] -= 1\n",
    "                state[3] += 1\n",
    "            if i == 'k':\n",
    "                if state[3] == 0:\n",
    "                    return -1\n",
    "                state[3] -= 1\n",
    "                state[4] += 1\n",
    "        if state[0] > 0:\n",
    "            return -1\n",
    "        return state[4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        dp=[0,0,0,0,0]\n",
    "        #de=[0,0,0,0,0]\n",
    "        hash1={'c':0,'r':1,'o':2,'a':3,'k':4}\n",
    "        for i in croakOfFrogs:\n",
    "            if dp[hash1[i]-1]>0:\n",
    "                dp[hash1[i]-1]-=1\n",
    "                dp[hash1[i]]+=1\n",
    "            elif i=='c':\n",
    "                if dp[-1]:\n",
    "                    dp[-1]-=1\n",
    "                dp[hash1[i]]+=1\n",
    "            elif dp[hash1[i]-1]==0:\n",
    "                return -1\n",
    "            else:\n",
    "                 pass\n",
    "\n",
    "                \n",
    "         \n",
    "            \n",
    "        for i in dp[:4]:\n",
    "            if i!=0:\n",
    "                return -1\n",
    "        return dp[-1]\n",
    "            # if i=='c':\n",
    "            #     dp[1]+=1\n",
    "            #     dp[0]-=1\n",
    "            # elif i=='r'\n",
    "            #     dp[2]+=1\n",
    "            #     dp[]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "TABLE = {'c':0, 'r':1, 'o':2, 'a':3, 'k':4}\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        l = [0] * 5\n",
    "        for c in croakOfFrogs:\n",
    "            l[i := TABLE[c]] += 1\n",
    "            if l[i - 1]:\n",
    "                l[i - 1] -= 1\n",
    "            elif i:\n",
    "                return -1\n",
    "            \n",
    "        \n",
    "        return -1 if any(l[:-1]) else l[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5:\n",
    "            return -1\n",
    "        res, frog_num = 0, 0\n",
    "        cnt = [0] * 4\n",
    "        mp = {'c':0, 'r':1, 'o':2, 'a':3, 'k':4}\n",
    "        for c in croakOfFrogs:\n",
    "            t = mp[c]\n",
    "            if t == 0:\n",
    "                cnt[t] += 1\n",
    "                frog_num += 1\n",
    "                if frog_num > res:\n",
    "                    res = frog_num\n",
    "            else:\n",
    "                if cnt[t - 1] == 0:\n",
    "                    return -1\n",
    "                cnt[t - 1] -= 1\n",
    "                if t == 4:\n",
    "                    frog_num -= 1\n",
    "                else:\n",
    "                    cnt[t] += 1\n",
    "        if frog_num > 0:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "TABLE = {'c':0, 'r':1, 'o':2, 'a':3, 'k':4}\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        l = [0] * 5\n",
    "        for c in croakOfFrogs:\n",
    "            i = TABLE[c]\n",
    "            l[i] += 1\n",
    "            if l[i - 1]:\n",
    "                l[i - 1] -= 1\n",
    "            elif i:\n",
    "                return -1\n",
    "        \n",
    "        return -1 if any(l[:-1]) else l[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        #在向量中，每一个位置代表一个青蛙，存放当前它发出的字母\n",
    "        #遍历字符串，匹配向量中的青蛙\n",
    "        #若为\"c\"，则加入一直青蛙，发声为c\n",
    "        #若为其他字母，找当前向量中的可以发出次声音二点蛙，若无则非法\n",
    "        #每只青蛙叫完后出队，统计队列最大长度\n",
    "\n",
    "        forgs = [0]*5\n",
    "        mp = {\n",
    "            \"c\": 0,\n",
    "            \"r\": 1,\n",
    "            \"o\": 2,\n",
    "            \"a\": 3,\n",
    "            \"k\": 4\n",
    "        }\n",
    "        \n",
    "        num = 0\n",
    "        ans = 0\n",
    "\n",
    "        for c in croakOfFrogs:\n",
    "            if c == \"c\":\n",
    "                forgs[0] += 1\n",
    "                num += 1\n",
    "                ans = max(ans, num)\n",
    "            else:\n",
    "                indx = mp[c]\n",
    "                if not forgs[indx - 1]:\n",
    "                    return -1\n",
    "\n",
    "                forgs[indx - 1] -= 1\n",
    "\n",
    "                if c == \"k\":\n",
    "                    num -= 1\n",
    "                else:\n",
    "                    forgs[indx] += 1\n",
    "        \n",
    "        return ans if not num else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        status = [0, 0, 0, 0, 0]\n",
    "        maxfrog = 0\n",
    "        for c in croakOfFrogs:\n",
    "            match c:\n",
    "                case 'c':\n",
    "                    status[0] += 1\n",
    "                case 'r':\n",
    "                    if status[0] == 0:\n",
    "                        return -1\n",
    "                    else:\n",
    "                        status[0] -= 1\n",
    "                        status[1] += 1\n",
    "                case 'o':\n",
    "                    if status[1] == 0:\n",
    "                        return -1\n",
    "                    else:\n",
    "                        status[1] -= 1\n",
    "                        status[2] += 1\n",
    "                case 'a':\n",
    "                    if status[2] == 0:\n",
    "                        return -1\n",
    "                    else:\n",
    "                        status[2] -= 1\n",
    "                        status[3] += 1\n",
    "                case 'k':\n",
    "                    if status[3] == 0:\n",
    "                        return -1\n",
    "                    else:\n",
    "                        status[3] -= 1\n",
    "                case _:\n",
    "                    return -1\n",
    "            maxfrog = max(sum(status), maxfrog)\n",
    "        return maxfrog if sum(status) == 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, s: str) -> int:\n",
    "        sound = \"croak\"\n",
    "        dp = [0] * len(sound)\n",
    "        \n",
    "        for c in s:\n",
    "            i = sound.index(c)\n",
    "            if i == 0:\n",
    "                if dp[4]: dp[4] -= 1\n",
    "                dp[i] += 1\n",
    "            elif dp[i - 1] == 0:\n",
    "                return -1\n",
    "            else:\n",
    "                dp[i] += 1\n",
    "                dp[i - 1] -= 1\n",
    "        if sum(dp) - dp[4] != 0:\n",
    "            return -1\n",
    "        return dp[4]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        self.c = 0\n",
    "        self.r = 0\n",
    "        self.o = 0\n",
    "        self.a = 0\n",
    "        self.k = 0\n",
    "        self.res = 0\n",
    "        self.busy = 0\n",
    "\n",
    "        for s in croakOfFrogs:\n",
    "            if s == \"c\":\n",
    "                if self.res > 0:\n",
    "                    self.busy += 1\n",
    "                    self.res -= 1\n",
    "                self.c += 1\n",
    "            elif s == \"r\":\n",
    "                self.r += 1\n",
    "            elif s == \"o\":\n",
    "                self.o += 1\n",
    "            elif s == \"a\":\n",
    "                self.a += 1\n",
    "            elif s == \"k\":\n",
    "                self.k += 1\n",
    "                self.res += 1\n",
    "\n",
    "            if not (self.c >= self.r >= self.o >= self.a >= self.k):\n",
    "                return -1\n",
    "        if self.c == self.r == self.o == self.a == self.k:\n",
    "            return self.c - self.busy\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        count = [0] * 5\n",
    "        frogs = max_frogs = 0\n",
    "        for i in croakOfFrogs:\n",
    "            n = \"croak\".find(i)\n",
    "            count[n] += 1\n",
    "            if n == 0:\n",
    "                max_frogs = max(max_frogs, count[0] - count[4])\n",
    "            elif count[n-1] < count[n]:\n",
    "                return -1\n",
    "        return max_frogs if count[0] == count[4] else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理每个字母在 \"croak\" 中的上一个字母\n",
    "PREVIOUS = dict(pairwise(\"croakc\"[::-1]))\n",
    "print(PREVIOUS)\n",
    "class Solution:\n",
    "    \n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        print(PREVIOUS)\n",
    "        cnt = Counter()\n",
    "        for ch in croakOfFrogs:\n",
    "            pre = PREVIOUS[ch]  # pre 为 ch 在 \"croak\" 中的上一个字母\n",
    "            if cnt[pre]:  # 如果有青蛙发出了 pre 的声音\n",
    "                cnt[pre] -= 1  # 复用一只\n",
    "            elif ch != 'c':  # 否则青蛙必须从 'c' 开始蛙鸣\n",
    "                return -1  # 不符合要求\n",
    "            cnt[ch] += 1  # 发出了 ch 的声音\n",
    "        if any(cnt[ch] for ch in \"croa\"):\n",
    "            return -1  # 有发出其它声音的青蛙，不符合要求\n",
    "        return cnt['k']  # 最后青蛙们都发出了 'k' 的声音\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        lst = [0] * 5\n",
    "        for ch in croakOfFrogs:\n",
    "            if ch == 'c':               \n",
    "                if lst[4]: \n",
    "                    lst[4] -= 1\n",
    "                lst[0] += 1                 \n",
    "            elif ch == 'r':\n",
    "                if lst[0]: \n",
    "                    lst[0] -= 1\n",
    "                    lst[1] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            elif ch == 'o':\n",
    "                if lst[1]: \n",
    "                    lst[1] -= 1\n",
    "                    lst[2] += 1\n",
    "                else:\n",
    "                    return -1         \n",
    "            elif ch == 'a':\n",
    "                if lst[2]: \n",
    "                    lst[2] -= 1\n",
    "                    lst[3] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            elif ch == 'k':\n",
    "                if lst[3]: \n",
    "                    lst[3] -= 1\n",
    "                    lst[4] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "        return -1 if any(lst[:4]) else lst[4]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5:\n",
    "            return -1\n",
    "        res, frog_num = 0, 0\n",
    "        cnt = [0] * 4\n",
    "        mp = {'c':0, 'r':1, 'o':2, 'a':3, 'k':4}\n",
    "        for c in croakOfFrogs:\n",
    "            t = mp[c]\n",
    "            if t == 0:\n",
    "                cnt[t] += 1\n",
    "                frog_num += 1\n",
    "                if frog_num > res:\n",
    "                    res = frog_num\n",
    "            else:\n",
    "                if cnt[t - 1] == 0:\n",
    "                    return -1\n",
    "                cnt[t - 1] -= 1\n",
    "                if t == 4:\n",
    "                    frog_num -= 1\n",
    "                else:\n",
    "                    cnt[t] += 1\n",
    "        if frog_num > 0:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5:\n",
    "            return -1\n",
    "        res, frog_num = 0, 0\n",
    "        cnt = [0] * 4\n",
    "        mp = {'c':0, 'r':1, 'o':2, 'a':3, 'k':4}\n",
    "        for c in croakOfFrogs:\n",
    "            t = mp[c]\n",
    "            if t == 0:\n",
    "                cnt[t] += 1\n",
    "                frog_num += 1\n",
    "                if frog_num > res:\n",
    "                    res = frog_num\n",
    "            else:\n",
    "                if cnt[t - 1] == 0:\n",
    "                    return -1\n",
    "                cnt[t - 1] -= 1\n",
    "                if t == 4:\n",
    "                    frog_num -= 1\n",
    "                else:\n",
    "                    cnt[t] += 1\n",
    "        if frog_num > 0:\n",
    "            return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        res = 0\n",
    "        croak = \"croak\"\n",
    "        frogs = [0] * 4\n",
    "        for c in croakOfFrogs:\n",
    "            index = croak.index(c)\n",
    "            if index == 0: \n",
    "                frogs[0] += 1\n",
    "                res = max(res, sum(frogs))\n",
    "                continue\n",
    "            if frogs[index - 1] == 0: return -1\n",
    "            else: \n",
    "                frogs[index - 1] -= 1\n",
    "                if index < 4: frogs[index] += 1   \n",
    "        for value in frogs:\n",
    "            if value != 0: return -1\n",
    "        return res\n",
    "        \n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        \n",
    "        # 状态转移字典，记录当前状态下，处于不同发声阶段的青蛙数量\n",
    "        state_rec = {'c':0, 'r':0, 'o':0, 'a':0, 'k':0}\n",
    "        max_fog = sum(list(state_rec.values()))\n",
    "        \n",
    "        for c in croakOfFrogs:\n",
    "            if c == 'c':\n",
    "                # 两种情况，一种是有青蛙叫完了一声，可以继续叫: k>0, k:-1, c:+1\n",
    "                # 另一种是没有青蛙叫完，k=0, c:+1\n",
    "                if state_rec['k'] > 0:  # 不会造成青蛙总数变化\n",
    "                    state_rec['k'] -= 1\n",
    "                    state_rec['c'] += 1\n",
    "                else:\n",
    "                    state_rec['c'] += 1\n",
    "                # end if else\n",
    "            elif c == 'r':\n",
    "                if state_rec['c'] == 0:     # 前置状态不满足\n",
    "                    return -1\n",
    "                else:\n",
    "                    state_rec['c'] -= 1\n",
    "                    state_rec['r'] += 1\n",
    "                # end if else\n",
    "            elif c == 'o':\n",
    "                if state_rec['r'] == 0:     # 前置状态不满足\n",
    "                    return -1\n",
    "                else:\n",
    "                    state_rec['r'] -= 1\n",
    "                    state_rec['o'] += 1\n",
    "                # end if else\n",
    "            elif c == 'a':\n",
    "                if state_rec['o'] == 0:     # 前置状态不满足\n",
    "                    return -1\n",
    "                else:\n",
    "                    state_rec['o'] -= 1\n",
    "                    state_rec['a'] += 1\n",
    "                # end if else\n",
    "            elif c == 'k':\n",
    "                if state_rec['a'] == 0:     # 前置状态不满足\n",
    "                    return -1\n",
    "                else:\n",
    "                    state_rec['a'] -= 1\n",
    "                    state_rec['k'] += 1\n",
    "                # end if else\n",
    "            else:\n",
    "                return -1\n",
    "            # end if else\n",
    "\n",
    "            now_fog = sum(list(state_rec.values()))\n",
    "            if now_fog > max_fog:\n",
    "                max_fog = now_fog\n",
    "        # end for\n",
    "\n",
    "        # 边界判断，如果有没叫完的，-1\n",
    "        for k in state_rec:\n",
    "            if k != 'k':\n",
    "                if state_rec[k] != 0:\n",
    "                    return -1\n",
    "        return max_fog\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        a = b = c = d = e = 0\n",
    "        for i in croakOfFrogs:\n",
    "            if i == 'c':\n",
    "                a += 1\n",
    "                if e > 0:\n",
    "                    e -= 1\n",
    "            elif i == 'r' and a > 0:\n",
    "                a -= 1\n",
    "                b += 1\n",
    "            elif i == 'o' and b > 0:\n",
    "                b -= 1\n",
    "                c += 1\n",
    "            elif i == 'a' and c > 0:\n",
    "                c -= 1\n",
    "                d += 1\n",
    "            elif i == 'k' and d > 0:\n",
    "                d -= 1\n",
    "                e += 1\n",
    "            else:\n",
    "                return -1\n",
    "        return e if a == b == c == d == 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs)%5 !=0 : return -1\n",
    "        ans = 0\n",
    "        count_list = {\"c\":0,\"r\":0,\"o\":0,\"a\":0,\"k\":0}\n",
    "        \n",
    "        for i in croakOfFrogs:\n",
    "            if i not in count_list:\n",
    "                return -1\n",
    "            else:\n",
    "                count_list[i] += 1\n",
    "\n",
    "            if not(count_list[\"c\"]>=count_list[\"r\"] and count_list[\"r\"]>=count_list[\"o\"] and count_list[\"o\"]>=count_list[\"a\"] and count_list[\"a\"]>=count_list[\"k\"]):\n",
    "                return -1\n",
    "            ans = max(ans,count_list[\"c\"]-count_list[\"k\"])\n",
    "        \n",
    "        if count_list[\"c\"]==count_list[\"r\"]==count_list[\"o\"]==count_list[\"a\"]==count_list[\"k\"]:\n",
    "            return ans\n",
    "        else:\n",
    "            return -1\n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        lst = [0] * 5\n",
    "\n",
    "        for ch in croakOfFrogs:\n",
    "            if ch == 'c':               \n",
    "                if lst[4]: \n",
    "                    lst[4] -= 1\n",
    "                lst[0] += 1                 \n",
    "            elif ch == 'r':\n",
    "                if lst[0]: \n",
    "                    lst[0] -= 1\n",
    "                    lst[1] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            elif ch == 'o':\n",
    "                if lst[1]: \n",
    "                    lst[1] -= 1\n",
    "                    lst[2] += 1\n",
    "                else:\n",
    "                    return -1         \n",
    "            elif ch == 'a':\n",
    "                if lst[2]: \n",
    "                    lst[2] -= 1\n",
    "                    lst[3] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            elif ch == 'k':\n",
    "                if lst[3]: \n",
    "                    lst[3] -= 1\n",
    "                    lst[4] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "                    \n",
    "        return -1 if any(lst[:4]) else lst[4]\n",
    "\n",
    "# 作者：_G_\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        c,r,o,a,k = 0,0,0,0,0\n",
    "        ret = 0\n",
    "        for i in croakOfFrogs:\n",
    "            if i == 'c':\n",
    "                c += 1\n",
    "                ret = max(c-k,ret)\n",
    "            elif c > r and i == 'r':\n",
    "                r += 1\n",
    "            elif r > o and i == 'o':\n",
    "                o += 1\n",
    "            elif o > a and i == 'a':\n",
    "                a += 1\n",
    "            elif a > k and i == 'k':\n",
    "                k += 1\n",
    "            else:return -1\n",
    "        return ret if c==r and c==o and c==a and c==k else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        n = len(croakOfFrogs)\n",
    "        ans = 0\n",
    "        hashmap ={'c':0,'r':0,'o':0,'a':0,'k':0}\n",
    "        for i in range(n):\n",
    "            if croakOfFrogs[i] == 'c':hashmap['c'] += 1\n",
    "            if croakOfFrogs[i] == 'r':hashmap['r'] += 1\n",
    "            if croakOfFrogs[i] == 'o':hashmap['o'] += 1\n",
    "            if croakOfFrogs[i] == 'a':hashmap['a'] += 1\n",
    "            if croakOfFrogs[i] == 'k':hashmap['k'] += 1\n",
    "            if not hashmap['c']>= hashmap['r'] >= hashmap['o'] >= hashmap['a'] >= hashmap['k']:\n",
    "                return -1\n",
    "            ans = max(ans,hashmap['c'] - hashmap['k'])\n",
    "        \n",
    "        return ans if hashmap['c']== hashmap['r'] == hashmap['o'] == hashmap['a'] == hashmap['k'] else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        lst = [0] * 5\n",
    "        for ch in croakOfFrogs:\n",
    "            if ch == 'c':               \n",
    "                if lst[4]: \n",
    "                    lst[4] -= 1\n",
    "                lst[0] += 1                 \n",
    "            elif ch == 'r':\n",
    "                if lst[0]: \n",
    "                    lst[0] -= 1\n",
    "                    lst[1] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            elif ch == 'o':\n",
    "                if lst[1]: \n",
    "                    lst[1] -= 1\n",
    "                    lst[2] += 1\n",
    "                else:\n",
    "                    return -1         \n",
    "            elif ch == 'a':\n",
    "                if lst[2]: \n",
    "                    lst[2] -= 1\n",
    "                    lst[3] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            elif ch == 'k':\n",
    "                if lst[3]: \n",
    "                    lst[3] -= 1\n",
    "                    lst[4] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "        return -1 if any(lst[:4]) else lst[4] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs)%5 != 0: return -1\n",
    "        waitforpair = {'r': 0, 'o': 0, 'a': 0, 'k':0}\n",
    "        Map = {'c':'r', 'r':'o', 'o':'a', 'a':'k'}\n",
    "        character_legal = {'c', 'r', 'o', 'a', 'k'}\n",
    "\n",
    "        res = 0\n",
    "        cnt = 0\n",
    "        for c in croakOfFrogs:\n",
    "            if c not in character_legal: return -1\n",
    "            if c != 'c':\n",
    "                if waitforpair[c] == 0: return -1\n",
    "                else: \n",
    "                    waitforpair[c] -= 1\n",
    "                    cnt -= 1\n",
    "            if c != 'k':\n",
    "                waitforpair[Map[c]] += 1\n",
    "                cnt += 1\n",
    "                res = max(res, cnt)\n",
    "            #print(cnt)\n",
    "            #print(waitforpair)\n",
    "        \n",
    "        if max(waitforpair.values()) == 0:\n",
    "            return res\n",
    "        else:\n",
    "            return -1\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5:\n",
    "            return -1\n",
    "        res, frog_num = 0, 0\n",
    "        cnt = [0] * 4\n",
    "        mp = {'c':0, 'r':1, 'o':2, 'a':3, 'k':4}\n",
    "        for c in croakOfFrogs:\n",
    "            t = mp[c]\n",
    "            if t == 0:\n",
    "                cnt[t] += 1\n",
    "                frog_num += 1\n",
    "                if frog_num > res:\n",
    "                    res = frog_num\n",
    "            else:\n",
    "                if cnt[t - 1] == 0:\n",
    "                    return -1\n",
    "                cnt[t - 1] -= 1\n",
    "                if t == 4:\n",
    "                    frog_num -= 1\n",
    "                else:\n",
    "                    cnt[t] += 1\n",
    "        if frog_num > 0:\n",
    "            return -1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理每个字母在 \"croak\" 中的上一个字母\n",
    "PREVIOUS = dict(pairwise(\"croakc\"[::-1]))\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        cnt = Counter()\n",
    "        for ch in croakOfFrogs:\n",
    "            pre = PREVIOUS[ch]  # pre 为 ch 在 \"croak\" 中的上一个字母\n",
    "            if cnt[pre]:  # 如果有青蛙发出了 pre 的声音\n",
    "                cnt[pre] -= 1  # 复用一只\n",
    "            elif ch != 'c':  # 否则青蛙必须从 'c' 开始蛙鸣\n",
    "                return -1  # 不符合要求\n",
    "            cnt[ch] += 1  # 发出了 ch 的声音\n",
    "        if any(cnt[ch] for ch in \"croa\"):\n",
    "            return -1  # 有发出其它声音的青蛙，不符合要求\n",
    "        return cnt['k']  # 最后青蛙们都发出了 'k' 的声音\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if not croakOfFrogs or len(croakOfFrogs) % 5 > 0: return -1\n",
    "\n",
    "        hash = {\n",
    "            'c': 0,\n",
    "            'r': 0,\n",
    "            'o': 0,\n",
    "            'a': 0,\n",
    "            'k': 0,\n",
    "        }\n",
    "\n",
    "        for c in croakOfFrogs:\n",
    "            if c == 'c':\n",
    "                if hash['k'] > 0:\n",
    "                    hash['k'] -= 1\n",
    "                hash[c] += 1\n",
    "            elif c == 'r':\n",
    "                if hash['c'] - 1 >= 0:\n",
    "                    hash['c'] -= 1\n",
    "                    hash[c] += 1\n",
    "                else: return -1\n",
    "            elif c == 'o':\n",
    "                if hash['r'] - 1 >= 0:\n",
    "                    hash['r'] -= 1\n",
    "                    hash[c] += 1\n",
    "                else: return -1\n",
    "            elif c == 'a':\n",
    "                if hash['o'] - 1 >= 0:\n",
    "                    hash['o'] -= 1\n",
    "                    hash[c] += 1\n",
    "                else: return -1\n",
    "            elif c == 'k':\n",
    "                if hash['a'] - 1 >= 0:\n",
    "                    hash['a'] -= 1\n",
    "                    hash[c] += 1\n",
    "                else: return -1\n",
    "            else: return -1\n",
    "\n",
    "        if hash['c'] > 0: return -1\n",
    "\n",
    "        return hash['k']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        d = {}\n",
    "        for i, c in enumerate(\"croak\"):\n",
    "            d[c] = i \n",
    "        cnt = Counter()\n",
    "        ans = 0\n",
    "        num = 0\n",
    "        for c in croakOfFrogs:\n",
    "            if d[c]:\n",
    "                if cnt[d[c] - 1]:\n",
    "                    cnt[d[c] - 1] -= 1\n",
    "                    if d[c] < 4:\n",
    "                        cnt[d[c]] += 1\n",
    "                    else:\n",
    "                        num -= 1\n",
    "                else:\n",
    "                    return -1\n",
    "            else:\n",
    "                cnt[0] += 1\n",
    "                num += 1\n",
    "                ans = max(ans, num)\n",
    "        return ans if sum(cnt.values()) == 0 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5 != 0:\n",
    "            return -1\n",
    "        croak = 'croak'\n",
    "        charDict = {c:0 for c in croak}\n",
    "        prevDict = {croak[i]:croak[i-1] for i in range(1,len(croak))}\n",
    "        frogs = 0\n",
    "        result = 0\n",
    "        for c in croakOfFrogs:\n",
    "            if c == 'c':\n",
    "                frogs += 1\n",
    "                charDict[c] += 1\n",
    "                if frogs > result:\n",
    "                    result = frogs\n",
    "            else:\n",
    "                if charDict[c] + 1 > frogs:\n",
    "                    return -1\n",
    "                elif charDict[c] + 1 > charDict[prevDict[c]]:\n",
    "                    return -1\n",
    "                charDict[c] += 1\n",
    "                if c == 'k':\n",
    "                    frogs -= 1\n",
    "                    for k in charDict:\n",
    "                        charDict[k] -= 1\n",
    "        \n",
    "        return result if frogs == 0 else -1\n",
    "                \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        # 无效的情况,剪枝\n",
    "        le = len(croakOfFrogs)\n",
    "        if le < 5 or croakOfFrogs[0] != 'c' or croakOfFrogs[-1] != 'k':\n",
    "            return -1\n",
    "\n",
    "        # c可以在任何位置出现，在字符串有效的情况下，c出现的个数和k出现个数之差最大值就是青蛙数，\n",
    "        # 同时，其他字母要保持严格的顺序不变，若果前一个字母的个数<后一个字母的个数，则字符串无效\n",
    "        cunt = {'c': 0, 'r': 0, 'o': 0, 'a': 0, 'k': 0, }\n",
    "        dic = {'r': 'c', 'o': 'r', 'a': 'o', 'k': 'a'}\n",
    "\n",
    "        res = 0\n",
    "        for ele in croakOfFrogs:\n",
    "            cunt[ele] += 1\n",
    "            if ele != 'c' and cunt[dic[ele]] < cunt[ele]:\n",
    "                return -1\n",
    "            if ele == 'c':\n",
    "                res = max(res, cunt[ele] - cunt['k'])\n",
    "        return res if len(set(cunt.values())) == 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5 != 0:  # 长度不是5的倍数, 不成立\n",
    "            return -1\n",
    "        cnt = [0, 0, 0, 0, 0]   # 分别表示c,r,o,a,k的出现次数\n",
    "        cur = 0     # 当前有多少只青蛙正在叫\n",
    "        res = 0     # 最终结果\n",
    "        for ch in croakOfFrogs:\n",
    "            res = max(res, cur) # 维护遍历过程中最多有多少只青蛙同时在叫\n",
    "            if ch == 'c':\n",
    "                cur += 1    # 需要一只青蛙开始叫\n",
    "                cnt[0] += 1\n",
    "            elif ch == 'r':\n",
    "                cnt[1] += 1\n",
    "                if cnt[1] > cnt[0]: # r的出现此处不能比c多，后续同理\n",
    "                    return -1\n",
    "            elif ch == 'o':\n",
    "                cnt[2] += 1\n",
    "                if cnt[2] > cnt[1]:\n",
    "                    return -1\n",
    "            elif ch == 'a':\n",
    "                cnt[3] += 1\n",
    "                if cnt[3] > cnt[2]:\n",
    "                    return -1\n",
    "            elif ch == 'k':\n",
    "                cur -= 1    # 有一只青蛙叫完了\n",
    "                cnt[4] += 1\n",
    "                if cnt[4] > cnt[3]:\n",
    "                    return -1\n",
    "        if len(set(cnt)) != 1: # c, r, o, a, k出现次数不相等\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        \n",
    "        checkposition = {'c':0,\"r\":0,\"o\":0,\"a\":0, \"k\":0}\n",
    "\n",
    "        count = 0\n",
    "\n",
    "        for croak in croakOfFrogs:\n",
    "            if croak == 'c':\n",
    "                checkposition['c'] += 1\n",
    "                if checkposition['k'] == 0:\n",
    "                    count += 1\n",
    "                else:\n",
    "                    checkposition['k'] -= 1\n",
    "\n",
    "            elif croak == 'r': \n",
    "                if checkposition['c'] > 0:\n",
    "                    checkposition['c'] -= 1\n",
    "                    checkposition['r'] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            \n",
    "            elif croak == 'o': \n",
    "                if checkposition['r'] > 0:\n",
    "                    checkposition['r'] -= 1\n",
    "                    checkposition['o'] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "            \n",
    "            elif croak == 'a': \n",
    "                if checkposition['o'] > 0:\n",
    "                    checkposition['o'] -= 1\n",
    "                    checkposition['a'] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "\n",
    "            elif croak == 'k': \n",
    "                if checkposition['a'] > 0:\n",
    "                    checkposition['a'] -= 1\n",
    "                    checkposition['k'] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "\n",
    "        if checkposition['c'] == checkposition['r'] == checkposition['o'] == checkposition['a'] ==0:\n",
    "            return count\n",
    "            \n",
    "        \n",
    "        return -1\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        if len(croakOfFrogs) % 5 != 0:\n",
    "            return -1\n",
    "        # 字母的出现分先后顺序 后一个字母出现前一个字母减一来表示顺序性\n",
    "        c_num, r_num, o_num, a_num, k_num = 0, 0, 0, 0, 0\n",
    "        ans = 0\n",
    "        for ch in croakOfFrogs:\n",
    "            if ch == 'c':\n",
    "                c_num += 1\n",
    "                # 如果当前字符为c 且没有记录的k 说明是新的一只青蛙叫\n",
    "                if k_num != 0:\n",
    "                    k_num -= 1\n",
    "                else:\n",
    "                    ans += 1\n",
    "            elif ch == 'r':\n",
    "                c_num -= 1\n",
    "                r_num += 1\n",
    "            elif ch == 'o':\n",
    "                r_num -= 1\n",
    "                o_num += 1\n",
    "            elif ch == 'a':\n",
    "                o_num -= 1\n",
    "                a_num += 1\n",
    "            elif ch == 'k':\n",
    "                a_num -= 1\n",
    "                k_num += 1\n",
    "            if c_num < 0 or r_num < 0 or o_num < 0 or a_num < 0 or k_num < 0:\n",
    "                break\n",
    "        # 判断按顺序的字母是否都安序排列了\n",
    "        if c_num != 0 or r_num != 0 or o_num != 0 or a_num != 0:\n",
    "            return -1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 预处理每个字母在 \"croak\" 中的上一个字母\r\n",
    "PREVIOUS = dict(pairwise(\"croakc\"[::-1]))\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\r\n",
    "        cnt = Counter()\r\n",
    "        for ch in croakOfFrogs:\r\n",
    "            pre = PREVIOUS[ch]  # pre 为 ch 在 \"croak\" 中的上一个字母\r\n",
    "            #print(ch, pre)\r\n",
    "            if cnt[pre]:  # 如果有青蛙发出了 pre 的声音\r\n",
    "                cnt[pre] -= 1  # 复用一只\r\n",
    "            elif ch != 'c':  # 否则青蛙必须从 'c' 开始蛙鸣\r\n",
    "                return -1  # 不符合要求\r\n",
    "            cnt[ch] += 1  # 发出了 ch 的声音\r\n",
    "        if any(cnt[ch] for ch in \"croa\"):\r\n",
    "            return -1  # 有发出其它声音的青蛙，不符合要求\r\n",
    "        return cnt['k']  # 最后青蛙们都发出了 'k' 的声音\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        self.c = 0\n",
    "        self.r = 0\n",
    "        self.o = 0\n",
    "        self.a = 0\n",
    "        self.k = 0\n",
    "        self.res = 0\n",
    "        self.busy = 0\n",
    "\n",
    "        for s in croakOfFrogs:\n",
    "            if s == \"c\":\n",
    "                if self.res > 0:\n",
    "                    self.busy += 1\n",
    "                    self.res -= 1\n",
    "                self.c += 1\n",
    "            elif s == \"r\":\n",
    "                self.r += 1\n",
    "            elif s == \"o\":\n",
    "                self.o += 1\n",
    "            elif s == \"a\":\n",
    "                self.a += 1\n",
    "            elif s == \"k\":\n",
    "                self.k += 1\n",
    "                self.res += 1\n",
    "\n",
    "            if not (self.c >= self.r >= self.o >= self.a >= self.k):\n",
    "                return -1\n",
    "        if self.c == self.r == self.o == self.a == self.k:\n",
    "            return self.c - self.busy\n",
    "        else:\n",
    "            return -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque, Counter\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        # 以c开始，以k结束，所以只要保证在字符串有效的情况下，k前面c的个数，减去k的个数的最大值+1，即是青蛙的个数\n",
    "        # 除c以外，所有字母都要顺序不变才有效，即前一个字母出现的次数不大于右面的字母出现的个数\n",
    "        # le = len(croakOfFrogs)\n",
    "        # if croakOfFrogs[0] != 'c' or croakOfFrogs[-1] != 'k' or le < 5:\n",
    "        #     return -1\n",
    "\n",
    "        # cunt = {'c': 1, 'r': 0, 'o': 0, 'a': 0, 'k': 0,}\n",
    "        # dic = {'r': 'c', 'o': 'r', 'a': 'o', 'k': 'a'}\n",
    "\n",
    "        # res = 0\n",
    "        # for i in range(1, le):\n",
    "        #     cur = croakOfFrogs[i]\n",
    "        #     cunt[cur] += 1\n",
    "        #     if cur == 'k':\n",
    "        #         res = max(res, cunt['c'] - cunt[cur] + 1)\n",
    "        #     if cur != 'c' and cunt[dic[cur]] < cunt[cur]:\n",
    "        #         return -1\n",
    "        # return res\n",
    "        le = len(croakOfFrogs)\n",
    "        if croakOfFrogs[0] != 'c' or croakOfFrogs[-1] != 'k' or le < 5:\n",
    "            return -1\n",
    "\n",
    "        cnt = {\"c\":0, \"r\":0, \"o\":0, \"a\":0, \"k\":0}\n",
    "        d = {\"r\":\"c\", \"o\":\"r\", \"a\":\"o\", \"k\":\"a\"}\n",
    "        ans = 0\n",
    "        for ch in croakOfFrogs:\n",
    "            cnt[ch] += 1\n",
    "            if ch != \"c\" and cnt[ch] > cnt[d[ch]]:\n",
    "                return -1\n",
    "            if ch == 'c' or ch == 'k':\n",
    "                ans = max(ans, cnt[\"c\"] - cnt[\"k\"])\n",
    "        return ans if len(set(cnt.values())) == 1 else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        l = []\n",
    "        d = {\"c\":-1, 'r':-1, 'o':-1, 'a':-1, 'k':-1}\n",
    "        ans = 1\n",
    "        for i in range(len(croakOfFrogs)):\n",
    "            if croakOfFrogs[i] == 'c':\n",
    "                l.append(0)\n",
    "                d['c'] += 1\n",
    "            elif croakOfFrogs[i] == 'k':\n",
    "                if len(l) > ans:\n",
    "                    ans = len(l)\n",
    "                if l[0] == 3:\n",
    "                    l.pop(0)\n",
    "                    for x in d.keys():\n",
    "                        d[x] -= 1\n",
    "            else:\n",
    "                d[croakOfFrogs[i]] += 1\n",
    "                if d['c']>=d['r'] and d['r']>=d['o'] and d['o']>=d['a'] and d['a']>=d['k']:\n",
    "                    l[d[croakOfFrogs[i]]] += 1\n",
    "                else:\n",
    "                    return -1\n",
    "        if len(l) > 0:\n",
    "            return -1\n",
    "        return ans\n",
    "\n",
    "\n",
    "            \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        res=[0]*5\n",
    "        maxx=0\n",
    "        dic={\n",
    "            \"c\":0,\n",
    "            \"r\":1,\n",
    "            \"o\":2,\n",
    "            \"a\":3,\n",
    "            \"k\":4\n",
    "        }\n",
    "        n=len(croakOfFrogs)\n",
    "        for c in croakOfFrogs:\n",
    "            cur=dic[c]\n",
    "            res[cur]+=1\n",
    "            maxx=max(maxx,res[cur])\n",
    "            if cur>0 and res[cur]>res[cur-1]:\n",
    "                return -1\n",
    "            if c==\"k\":\n",
    "                for i in range(5):\n",
    "                    res[i]-=1 \n",
    "        if res[0]>res[4]:\n",
    "            return -1\n",
    "        return maxx"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfFrogs(self, croakOfFrogs: str) -> int:\n",
    "        c=croakOfFrogs\n",
    "        re=0\n",
    "        if len(croakOfFrogs)%5!=0:return -1\n",
    "        stdic={'r':'c','o':'r','a':'o','k':'a','c':'k'}\n",
    "        dic={i:0 for i in 'croak'}\n",
    "        for i in range(len(c)):\n",
    "            if c[i]=='c':\n",
    "                dic['c']+=1\n",
    "                if dic['k']==0:re+=1\n",
    "                else:dic['k']-=1\n",
    "            else:\n",
    "                if dic[stdic[c[i]]]==0:return -1\n",
    "                else:\n",
    "                    dic[stdic[c[i]]]-=1\n",
    "                    dic[c[i]]+=1\n",
    "        if dic['c']!=0 or dic['r']!=0 or dic['o']!=0 or dic['a']!=0: return -1\n",
    "        return re"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
